package com.algorithms.techniques;

public class BinarySearchTree<K extends Comparable<K>, V> {
	protected Node<K, V> root = null;

	public Node<K, V>  insertInTree(Node<K, V> node) {
		if (getRoot() == null) {
			root = node;
			return root;
		}
		Node<K, V> traverseNode = root;
		Node<K, V> parent = root;
		while (traverseNode != null) {

			if (node.getKey().compareTo(traverseNode.getKey()) > 0) {
				traverseNode = traverseNode.getRightChild();
				if (parent.getRightChild() != null)
					parent = parent.getRightChild();
			} else if (node.getKey().compareTo(traverseNode.getKey()) < 0) {
				traverseNode = traverseNode.getLeftChild();
				if (parent.getLeftChild() != null)
					parent = parent.getLeftChild();
			} else {
				return traverseNode ;
			}

		}
		/*
		 * Set the child
		 */
		node.setParent(parent);
		if (node.getKey().compareTo(parent.getKey()) > 0) {
			parent.setRightChild(node);
		} else if (node.getKey().compareTo(parent.getKey()) < 0) {
			parent.setLeftChild(node);
		}
		return node;
	}

	public void inorderWalk(Node<K, V> currentNode) {
		if (currentNode == null)
			return;
		inorderWalk(currentNode.getLeftChild());
		System.out.println(currentNode);
		inorderWalk(currentNode.getRightChild());
	}

	public void insertIntegerInTree(BinarySearchTree<Integer, Integer> tree,
			int key) {
		Node<Integer, Integer> traverseNode = new Node<Integer, Integer>();
		traverseNode.setKey(key);
		traverseNode.setValue(key);
		tree.insertInTree(traverseNode);
	}

	public Node<K, V> getRoot() {
		return root;
	}

	public Node<K,V> searchNode(K key)
	{
		Node<K, V> traverseNode = root;
		while (traverseNode != null) {

			if (key.compareTo(traverseNode.getKey()) > 0) {
				traverseNode = traverseNode.getRightChild();
				
			} else if (key.compareTo(traverseNode.getKey()) < 0) {
				traverseNode = traverseNode.getLeftChild();
				
			} else 
			{
				return traverseNode;
			}
		}
		return null;
	}
	
	public Node<K,V> findSuccessor(K key)
	{
		Node<K,V> node =searchNode(key);
		return findSuccessorFromNode(node);
		
	}
	public Node<K,V> findSuccessorFromNode(Node<K,V> node )
	{
		
		if(node!=null)
		{
			if(node.getRightChild()!=null)
				return findSmallestFromNodeDown( node.getRightChild());
			Node<K,V> parent = node.getParent();
			while(parent!=null)
			{
				if(node.equals(parent.getLeftChild()))
				{
					return parent;
				}
				parent=parent.getParent();
				node=node.getParent();
			}
		}
		return null;
	}
	
	public Node<K,V> findSmallestFromRoot()
	{
		Node<K, V> traverseNode = root;
		while(traverseNode.getLeftChild()!=null )
		{
			traverseNode = traverseNode.getLeftChild();
		}
		return traverseNode;
	}
	
	public Node<K,V> findLargestFromRoot()
	{
		Node<K, V> traverseNode = root;
		while(traverseNode.getRightChild()!=null )
		{
			traverseNode = traverseNode.getRightChild();
		}
		return traverseNode;
	}
	
	public Node<K,V> findSmallestFromNodeDown( Node<K,V> startNode)
	{
		Node<K, V> traverseNode = startNode;
		while(traverseNode.getLeftChild()!=null )
		{
			traverseNode = traverseNode.getLeftChild();
		}
		return traverseNode;
	}
	
	public Node<K,V> findLargestFromNodeDown( Node<K,V> startNode)
	{
		Node<K, V> traverseNode = startNode;
		while(traverseNode.getRightChild()!=null )
		{
			traverseNode = traverseNode.getRightChild();
		}
		return traverseNode;
	}
	
	public void deleteKey(final K key)
	{
		final Node<K,V> node =searchNode(key);
		/*
		 * if the key is aleaf
		 */
		if(node.getLeftChild()==null && node.getRightChild()==null )
		{
			if(node.equals(node.getParent().getLeftChild()) )
				node.getParent().setLeftChild(null);
			if(node.equals( node.getParent().getRightChild()))
				node.getParent().setRightChild(null);
			return;
		}
		/*
		 * If the key is a node having no right child
		 */
		if(node.getLeftChild()!=null && node.getRightChild()==null )
		{
			if(node.equals(node.getParent().getLeftChild()) )
				node.getParent().setLeftChild(node.getLeftChild());
			if(node.equals( node.getParent().getRightChild()))
				node.getParent().setRightChild(node.getLeftChild());
			node.getLeftChild().setParent(node.getParent());
			return;
		}
		/*
		 * If the key is a node having both  child
		 */
		final Node<K,V> successor =findSuccessorFromNode(node);
		successor.setLeftChild(node.getLeftChild());
		if(node.getRightChild().equals(successor))
		{
			//successor.setRightChild(null);
		}
		else
		{
			/*
			 * when the right child of a successor is not null which forces to takes the 
			 * right child of the successor and set its parent to the
			 * succussor's parent.
			 */
			Node<K,V> successorRightChild =successor.getRightChild();
			if(successorRightChild!=null)
			{
				if(successor.equals(successor.getParent().getLeftChild()) )
					successor.getParent().setLeftChild(successorRightChild);
				if( successor.equals(successor.getParent().getRightChild()))
					successor.getParent().setRightChild(successorRightChild);
			}
			successor.setRightChild(node.getRightChild());
		}
		successor.setParent(node.getParent());
		if(node.getParent()!=null)
		{
			/*
			 * Set the successor to point to the parent of the deleted node
			 */
			if(node.equals(node.getParent().getLeftChild()) )
				node.getParent().setLeftChild(successor);
			if( node.equals(node.getParent().getRightChild()))
				node.getParent().setRightChild(successor);
		}
		else
		{
			//If you are deleting a root
			root=successor;
		}
	}
	
	public void leftRotate(K key)
	{
		final Node<K,V> node =searchNode(key);
		leftRotate(node);
	}
	public void leftRotate(Node<K,V> node)
	{
		Node<K,V> rightChild= node.getRightChild();
		/*
		 * Assign the left child of the above rightchild to node
		 */
		if(rightChild!=null)
		{
			if(rightChild.getLeftChild()!=null)
			{
				node.setRightChild(rightChild.getLeftChild());
				rightChild.getLeftChild().setParent(node);
			}
			else
			{
				node.setRightChild(null);
			}
			//Set the parent of above rightchild  
			rightChild.setParent(node.getParent());
			if(!root.equals(node))
			{
				if(node.equals(node.getParent().getLeftChild()) )
					node.getParent().setLeftChild(rightChild);
				if( node.equals(node.getParent().getRightChild()))
					node.getParent().setRightChild(rightChild);
			}
			else
			{
				root=rightChild;
			}
			//Set the input node parent
			node.setParent(rightChild);
			rightChild.setLeftChild(node);
		} 
	}
	
	public void rightRotate(K key)
	{
		final Node<K,V> node =searchNode(key);
		rightRotate(node);
	}
	public void rightRotate( Node<K,V> node)
	{
		Node<K,V> leftChild= node.getLeftChild();
		/*
		 * Assign the right child of the above rightchild 
		 */
		if(leftChild!=null)
		{
			if(leftChild.getRightChild()!=null)
			{
				node.setLeftChild(leftChild.getRightChild());
				leftChild.getRightChild().setParent(node);
			}
			else
			{
				node.setLeftChild(null);
			}
			//Set the parent of above rightchild and child of parent of the ode 
			leftChild.setParent(node.getParent());
			if(!root.equals(node))
			{
				if(node.equals(node.getParent().getLeftChild()) )
					node.getParent().setLeftChild(leftChild);
				if( node.equals(node.getParent().getRightChild()))
					node.getParent().setRightChild(leftChild);
			}
			else
			{
				root=leftChild;
			}
			//Set the input node parent
			node.setParent(leftChild);
			leftChild.setRightChild(node);
		} 
	}
	
}
